package immutablecollections;

import immutablecollections.ImShelf.ImShelfIterator;
import immutablecollections.exceptions.*;
import immutablecollections.functions.*;
import java.util.*;

/**
 * A zipper on an {@link ImShelf} lets you navigate back and forth in the shelf and "mutate" it as you go.
 * 
 * `ImShelfZipper` is to `ImShelf` what `java.util.ListIterator` is to `java.util.List`. It is a cursor that lets you
 * navigate back and forward within a shelf and to add/replace/delete elements relative to the current position.
 * 
 * Of course, since `Im` collections
 * are immutable, you cannot *actually* mutate the underlying shelf.
 * Instead, methods that "mutate" the zipper return new zippers.
 * For example {@link #next()} returns a *new* zipper pointing to the next element in the shelf
 * leaving the original zipper unchanged. After "mutating" the zipper, you have to use {@link #close()}
 * which returns the new shelf with the changes made to it.
 * 
 * ### next() and prev() and the "pair of lists" analogy
 * 
 * A good way to think of a shelf zipper is as a pair of lists formed out of the original shelf.
 * The *focus* element is the last element of the first list (if there is one).
 * 
 * If we consider the shelf `[1, 2, 3]`, when we get a zipper on it we get: 
 * 
 *     [] [1, 2, 3]
 * 
 * The first list is empty and the second list is just the list of the elements in the original shelf. In this state, there is no focus element.
 * 
 * If we use `next()` we get a new zipper:
 * 
 *     [1] [2, 3]
 *     
 * To "mutate" the zipper you can only operate on the focus - the last element of the first list. You can remove/replace it
 * and add elements after it.
 * 
 * You can get these lists from a zipper - see {@link #getFirst()} and {@link #getSecond()}.
 * 
 * This class is very similar in functionality to {@link ImListZipper}. The only significant
 * differences are in the performance -
 * closing a list zipper is **`O`**`(n)` where `n`is the size of the first list whereas closing a shelf zipper is
 * **`O`**`(log p)` where `p` is the maximum of the sizes of the two lists.
 * 
 * Inserting a list of size `n` into a list zipper is **`O`**`(n)` but inserting the same sized shelf into a
 * shelf zipper of size `m` is **`O`**`(log max(m,n))`.
 * 
 * See {@link ImListZipper} for more examples and description.
 * 
 * ### An Example
 * 
 * We start by creating a shelf:
 * 
 *     ImShelf<Integer> shelf = ImShelf.onArray(2, 3);     
 * 
 * Create a zipper on it:
 * 
 *     ImShelfZipper<Integer> start = shelf.getZipper();
 * 
 * It is in the initial state - the first list is empty:
 * 
 *     start  =>  [] [2, 3]
 *
 * Go to the next element:
 * 
 *     ImShelfZipper<Integer> z = start.next();
 *     
 *     z  =>  [2] [3]
 * 
 * Replace an element:
 * 
 *     z = z.setFocus(8);
 *     
 *     z  =>  [8] [3]
 *
 * Go back:
 * 
 *     z = z.prev();
 *     
 *     z  =>  [] [8, 3]
 * 
 * Push a new element element onto the first list:
 * 
 *     z = z.push(0);
 *     
 *     z  =>  [0] [8, 3]
 *
 * Push a shelf of elements onto the first list:
 * 
 *     z = z.pushAll(ImShelf.onArray(5, 13));
 *     
 *     z  =>  [0, 5, 13] [8, 3]
 *     
 * Move back:
 *     
 *     z = z.prev();
 *     
 *     z  =>  [0, 5] [13, 8, 3]
 *     
 * Pop an element off the first list:
 * 
 *     z = z.pop();
 *     
 *     z  =>  [0] [13, 8, 3]
 * 
 * Closing the zipper gives us the new "modified" shelf:
 * 
 *     z.close()  =>  [0, 13, 8, 3]
 *  
 * Of course, the original shelf has not changed:
 *     
 *     shelf  =>  [0, 13, 8, 3]
 *     
 * And indeed the original zipper has not changed. If you close a zipper without making any changes then
 * you just get back the original shelf:
 * 
 *     start.close() == shelf         =>  true
 *     start.next().close() == shelf  =>  true
 *     
 * See the <a href="{@docRoot}/immutablecollections/package-summary.html">package summary</a>
 * for more details of zippers.
 * 
 * 
 * @see ImShelf
 * @see ImShelfIterator
 * @see ImShelfZipperIterator
 * @see ImListZipper
 * 
 *
 */
public class ImShelfZipper<T> implements Iterable<ImShelfZipper<T>>
{
    final private ImTreeZipper<T> treeZipper;

    final private ImShelf<T> shelf;

    ImShelfZipper(ImShelf<T> shelf, ImTreeZipper<T> treeZipper)
    {
        this.shelf = shelf;
        this.treeZipper = treeZipper;
    }

    /**
     * The zipper whose focus is the next element in the shelf.
     * 
     * The first element of the second list is moved to the end of the first list:
     * 
     *     [1] [2, 3] next()  => [1, 2] [3]
     * 
     * @throws NoSuchElementException if no such element exists
     */
    public ImShelfZipper<T> next()
    {
        ImMaybe<ImTreeZipper<T>> next = treeZipper.next();

        if (next.hasValue())
            return new ImShelfZipper<T>(shelf, next.getValue());
        else
            throw new NoSuchElementException();
    }

    /**
     * The zipper whose focus is the previous element in the first list (if there is one).
     * 
     * The last element of the first list (if there is one) is moved to the front of the second list:
     * 
     *     [1, 2] [3] prev()    => [1] [2, 3]
     *     [1] [2, 3] prev()    => [] [1, 2, 3]
     *     
     * If the first list is empty then `this` is returned.
     * 
     *     [] [1, 2, 3] prev()  => [] [1, 2, 3]
     * 
     * If the first list is now empty then you won't be able to set or get the focus or pop it.
     * 
     * Note that this means that you can always use `prev()` on a zipper - even if {@link #hasPrev()} is `false`
     */
    public ImShelfZipper<T> prev()
    {
        ImMaybe<ImTreeZipper<T>> prev = treeZipper.previous();

        return prev.hasValue()
                ? new ImShelfZipper<T>(shelf, prev.getValue())
                : this;
    }

    /**
     * Return the shelf that the zipper represents, with all modifications made.
     * 
     * The lists are joined together:
     * 
     *     [1, 2] [3] close()  => [1, 2, 3]
     */
    public ImShelf<T> close()
    {
        ImTree<T> newTree = treeZipper.close();

        return newTree == shelf.getTree()
                // If the tree is the same then the shelf must be the same
                ? shelf
                : new ImShelf<T>(newTree);
    }

    /**
     * The zipper that is the same as `this` except that the focus element is `newElement`.
     * 
     *     [1] [2, 3] setFocus(5)    => [5] [2, 3]
     *     [] [1, 2, 3] setFocus(5)  => throws ZipperHasNoFocusException
     *     
     * @throws NoSuchElementException if the first list is empty
     */
    public ImShelfZipper<T> setFocus(T newElement)
    {
        return new ImShelfZipper<T>(shelf, treeZipper.replaceElement(newElement));
    }

    /**
     * Return the focus.
     * 
     *     [1] [2, 3] getFocus()    =>  1
     *     [] [1, 2, 3] getFocus()  =>  throws ZipperHasNoFocusException
     *     
     * @throws ZipperHasNoFocusException if the first list is empty
     */
    public T getFocus()
    {
        if (treeZipper.getElement() == null)
            throw new ZipperHasNoFocusException();
        else
            return treeZipper.getElement();
    }

    /**
     * The zipper that is the same as `this` but with `newElement` pushed onto the first list.
     * 
     *     [1] [2, 3] push(5)    =>  [1, 5] [2, 3]
     *     [] [1, 2, 3] push(5)  =>  [5] [1, 2, 3]
     * 
     * The new focus is `newElement`.
     */
    public ImShelfZipper<T> push(T newElement)
    {
        return new ImShelfZipper<T>(shelf, treeZipper.insertAfter(ImTree.newLeaf(newElement)));
    }

    /**
     * The zipper that is `this` but with `shelfToInsert` pushed onto the first list.
     * 
     * The new focus is the last element of `elementsToInsert`.
     * 
     *     [1] [2, 3] push([5, 8, 13])  =>  [1, 5, 8, 13] [2, 3]
     *     [] [] push([5, 8, 13])       =>  [5, 8, 13] []
     * 
     */
    public ImShelfZipper<T> pushAll(ImShelf<T> shelfToInsert)
    {
        return new ImShelfZipper<T>(shelf, treeZipper.insertAfter(shelfToInsert.getTree()));
    }

    /**
     * The zipper that is `this` but with the last element popped from the first list.
     * 
     *     [1] [2, 3] pop()  =>  [1] [2, 3]
     *     [] [1] pop()      =>  throws ZipperHasNoFocusException
     * 
     * 
     * @throws NoSuchElementException if the first list is empty
     */
    public ImShelfZipper<T> pop()
    {
        if (getIndex() == 0)
            throw new ZipperHasNoFocusException();
        else
            return new ImShelfZipper<T>(shelf, treeZipper.removeNode());
    }

    /**
     * The index of the focus - the size of the first list.
     * 
     *     [1, 5, 8, 13] [2, 3] getIndex()  =>  4
     * 
     */
    public int getIndex()
    {
        return treeZipper.getRank();
    }

    /**
     * A string representation of this zipper.
     * 
     *     ImShelf.empty().getZipper().toString()  =>  "[] []"
     *     
     *     ImShelfZipper<Integer> z = ImShelf.onArray(1, 2, 3).getZipper();
     *     
     *     z.toString()                      =>  "[] [1, 2, 3]"
     *     z.next().toString()               =>  "[1] [2, 3]"
     *     z.next().next().toString()        =>  "[1, 2] [3]"
     *     z.next().next().next().toString() =>  "[1, 2, 3] []"
     * 
     */
    @Override
    public String toString()
    {
        return "" + getFirst() + " " + getSecond();
    }

    /**
     * A string representation of this zipper that uses the function `fn` on each element to get its string representation.
     * 
     * If this method was defined:
     * 
     *     public static String star(Object o)
     *     {
     *         return "*";
     *     }
     * 
     * then:
     *    
     *     Function1<String> starFn = FnFactory.on(this).getFnStatic(String.class, "star", Object.class);
     *     
     *     ImShelfZipper<String> z = ImShelf.onArray("Yabba", "dabba", "do").getZipper();
     *     
     *     z.next().toString(starFn)  =>  "[*] [*, *]"
     * 
     * @see immutablecollections.functions
     */
    public String toString(Function1<String> fn)
    {
        return getFirst().toString(fn) + " " + getSecond().toString(fn);
    }

    /**
     * The first list.
     * 
     *     [1, 5, 8, 13] [2, 3] getFirst()  =>  [1, 5, 8, 13]
     * 
     */
    public ImList<T> getFirst()
    {
        return ImList.onAll(close()).take(getIndex());
    }

    /**
     * The second list.
     * 
     *     [1, 5, 8, 13] [2, 3] getSecond()  =>  [2, 3]
     * 
     */
    public ImList<T> getSecond()
    {
        return ImList.onAll(close()).drop(getIndex());
    }

    /**
     * `true` if there are more elements after the focus.
     * 
     *     [1] [2, 3] hasNext()  =>  true
     *     [] []      hasNext()  =>  false
     *     
     */
    public boolean hasNext()
    {
        return treeZipper.getAfterSize() > 0;
    }

    /**
     * `true` if there are more elements before the focus.
     * 
     *     [1, 2] [3] hasPrev()  =>  true
     *     [1] [2, 3] hasPrev()  =>  false
     *     [] [1]     hasPrev()  =>  false
     *     
     * Note that you can use {@link #prev()} even if `hasPrev()` is `false`.
     */
    public boolean hasPrev()
    {
        return getIndex() > 1;
    }

    /**
     * A zipper iterator on `this`.
     */
    @Override
    public Iterator<ImShelfZipper<T>> iterator()
    {
        return new ImShelfZipperIterator<T>(this);
    }

}
